package SubjectTree.One;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import Utility.TreeNode;

public class RightSideView {

/**
 * 难度：中等
 * 
 * 199. 二叉树的右视图
 * 	给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * 
 * 示例:
 * 	输入: [1,2,3,null,5,null,4]
 * 	输出: [1, 3, 4]
 * 	解释:
 * 	   1            <---
 * 	 /   \
 * 	2     3         <---
 * 	 \     \
 * 	  5     4       <---
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		RightSideView rsv = new RightSideView();
		TreeNode root = TreeNode.MkTree("[1,2,3,null,5,null,4]");
		System.out.println(rsv.rightSideView(root));
	}

	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> list = new ArrayList<>();
		if(root==null)return list;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			List<Integer> temp = new ArrayList<>();
			int currentLevelSize = queue.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = queue.poll();
				temp.add(node.val);
				if(node.left!=null)queue.offer(node.left);
				if(node.right!=null)queue.offer(node.right);
			}
			list.add(temp.get(temp.size()-1));
		}
		return list;
    }
}
